import java.util.Arrays;

/**
 *面试题 17.04. 消失的数字
 * https://leetcode.cn/problems/missing-number-lcci/description/
 *     1、哈希表
 *     2、直接遍历找出
 *     3、位操作^
 *     4、数学（高斯求和公式）
 *     5、二分查找
 */

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        int left = 0, right = len - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == mid) left = mid + 1;
            else right = mid;
        }
        if(left == nums[left]) return left + 1;//处理边界问题
        return left;
    }
}